package hunglv4.vnu;

import java.util.ArrayList;

public class Quicksort {
	private ArrayList<Integer> numbers;
	private int number;

	public void sort(ArrayList<Integer> values) {
		if (values == null || values.size() == 0) {
			return;
		}
		this.numbers = values;
		number = values.size();
		quicksort(0, number - 1);
	}

	private void quicksort(int low, int high) {
		int i = low, j = high;
		int pivot = numbers.get(low + (high - low) / 2);
		
		while (i <= j) {
			while (numbers.get(i) < pivot) {
				i++;
			}

			while (numbers.get(j) > pivot) {
				j--;
			}

			if (i <= j) {
				exchange(i, j);
				i++;
				j--;
			}
		}
		if (low < j)
			quicksort(low, j);
		if (i < high)
			quicksort(i, high);
	}

	private void exchange(int i, int j) {
		int temp = numbers.get(i);
		numbers.set(i, numbers.get(j));
		numbers.set(j, temp);
	}
}